//https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.videopod.episodes&vd_source=d6fe65f095f01f05591e89d810720ccc&p=20
// 2024-10-22

import java.util.Arrays;

public class P030_预测赢家_动态规划 {

    public static void main(String[] args) {
        System.out.println(fun(new int[] {5,200,1,6}));

    }

    private static boolean fun(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int player1 = maxScore(nums,0,nums.length-1);
        int player2 = sum - player1;
        return player1 > player2;
    }

    private static int maxScore(int[] arr,int l,int r) {
        if (l == r) return arr[l];
        int sLeft = 0,sRight = 0;
        if (r - l == 1) {
            sLeft = arr[l]; //左边分数
            sRight = arr[r];//右边分数
        }
        if (r - l > 1) {
            // 选取的最左边
            sLeft = arr[l] + Math.min(maxScore(arr,l+2,r),maxScore(arr,l+1,r-1));
            // 选取的最右边
            sRight = arr[r] + Math.min(maxScore(arr,l,r-2),maxScore(arr,l+1,r-1));
        }

        return Math.max(sLeft,sRight);
    }

}
